11058. Погоня за бабочкой
Ясными летними днями Нюша любит
ловить бабочек на свежем воздухе. Сегодня ей попалась хитрая бабочка: она
залетела в лабиринт и хотела скрыться в нем от Нюши.
Лабиринт состоит из n комнат, пронумерованных от 1 до n, некоторые
из которых соединены между собой коридорами. Известно, что между любыми двумя
комнатами существует единственный путь из коридоров. Иными словами, лабиринт
представляет собой дерево, и количество коридоров равно n – 1.
Вход в лабиринт расположен в
комнате с номером 1. Будем называть листом любую комнату лабиринта,
которая соединена коридором ровно с одной другой комнатой и не совпадает при
этом с корнем. В каждом из листов располагается выход из лабиринта. Бабочка
летит от входа по направлению к одному из листов. Она летит с постоянной скоростью
и не разворачивается. Все коридоры имеют одинаковую длину, и за одну минуту
бабочка пролетает один коридор, перемещаясь в соседнюю комнату.
Для поимки бабочки Нюша решила
позвать несколько своих друзей. Исходно каждый из друзей может расположиться в
любой из комнат, содержащих выход. В тот момент, когда бабочка начнет лететь от
входа в лабиринт к одному из выходов, каждый из друзей может начать двигаться
из своей комнаты по направлению ко входу. Друзья двигаются с такой же
скоростью, что и бабочка. Если кто-то из друзей оказался в одной точке (в
комнате или в середине одного из коридоров) с бабочкой, то бабочка считается
пойманной. Если же бабочка долетит до вершины с выходом, не встретив никого из
друзей по пути, она благополучно выпорхнет из лабиринта и улетит на свободу.
Помогите Нюше определить, какое
минимальное число друзей понадобится для того, чтобы гарантированно поймать
бабочку, вне зависимости от того, к какому выходу она полетит.
Вход. Первая строка содержит целое число n (2 ≤ n ≤ 200000) – количество комнат в лабиринте.
В следующих n – 1 строках содержатся описания коридоров, соединяющих комнаты. Каждая из этих
строк содержит два целых числа u и v (1 ≤ u, v ≤ n, u ≠ v) – номера комнат, которые соединяет коридор. Гарантируется, что структура коридоров
представляет собой дерево.
Выход. Выведите одно целое число – минимальное количество друзей, необходимое для того, чтобы гарантированно поймать
бабочку.
|
Пример
входа 1 |
Пример
выхода 1 |
|
3 1 2 1 3 |
2 |
|
|
|
|
Пример
входа 2 |
Пример
выхода 2 |
|
4 1 2 2 3 2 4 |
1 |
РЕШЕНИЕ
графы –
поиск в глубину
Анализ
алгоритма
Запустим поиск в глубину из вершины 1. Для каждой вершины вычислим
два значения:
·
d[v] – расстояние от вершины 1 до v.
Если p – родитель v, то
d[v]
= d[p] + 1
·
h[v] – расстояние от вершины v до ближайшего листа в поддереве с корнем v.
Если to1,
to2, …, tok – сыновья v, то
h[v]
= 1 + min(h[to1], h[to2], …, h[tok])
Если v – лист дерева, то положим h[v]
= 0.
Запустим второй обход в глубину вершин дерева. В нем будем
вычислять ответ res[v] для вершины v: минимальное количество друзей, которое следует поставить в
некоторые из листьев этого поддерева, чтобы гарантированно поймать бабочку при
условии, что она обязательно полетит в это поддерево.
Если h[v] ≤ d[v], то res[v] = 1. Достаточно поставить одного друга в лист с минимальной
глубиной и до вершины v он доберется не позже чем бабочка
из корня до v. Иначе если to1,
to2, …, tok – сыновья v, то
res[v]
= res[to1] + res[to2] + … + res[tok]
Если мы не словим бабочку в вершине v, то следует быть готовым ловить ее в любом из поддеревьев
сыновей вершины v.
Ответом на задачу будет число res[1].
Пример
Для первого примера (рисунок слева) требуются два друга,
которых следует расположить в двух выходах. Бабочка может из вершины 1 может
полететь или в вершину 2 или в 3. Но и там и там ее поймает друг Нюши.
Во втором примере (рисунок справа) достаточно одного друга,
которого можно расположить в любом из двух выходов – вершине номер 3 или 4. За
одну минуту бабочка из вершины 1 переместится в вершину 2. Друг через 1 минуту
будет в вершине 2, где и поймает бабочку.
Рассмотрим следующий пример.
Для поимки бабочки Нюше нужны три друга.
Реализация алгоритма
Объявим константу бесконечность и
рабочие массивы.
#define INF 2000000000
vector<vector<int>
> g;
vector<int> d, h, res;
Функция
dfs (v, p, cnt) совершает обход в глубину из вершины v и возвращает значение h[v]. Предком вершины v является p. Расстояние от вершины 1 до v равно cnt. Для каждой вершины v вычисляем значения d[v]
и h[v].
int dfs(int v, int p = -1, int cnt = 0)
{
Расстояние от вершины 1 до v равно cnt, заносим его в d[v].
d[v] = cnt;
int height = INF;
Перебираем сыновей вершины v.
Рассматриваем ребро v → to. Если to совпадает с предком v (to = p), то
переходим к следующему сыну.
for (int to : g[v])
if (to !=
p)
В переменной height
вычисляем min(h[to1], h[to2],
…, h[tok]), где to1,
to2, …, tok – сыновья v.
height = min(height, dfs(to, v, cnt + 1));
Если height = INF, то v является листом и следует установить h[v]
= 0.
Иначе возвращаем h[v] = 1 + min(h[to1],
h[to2], …, h[tok]).
return h[v] =
(height == INF) ? 0 : 1 + height;
}
Функция
dfs2 (v, p) совершает обход в глубину из вершины v и возвращает значение res[v]. Предком вершины v является p.
int dfs2(int v, int p = -1)
{
int s = 0;
Пусть to1,
to2, …, tok – сыновья v. В
переменной s вычислим
значение суммы res[to1] + res[to2]
+ … + res[tok].
if (to !=
p)
{
dfs2(to, v);
s +=
res[to];
}
Если h[v] ≤ d[v], то достаточно одного друга и res[v] = 1.
Иначе res[v] = res[to1]
+ res[to2] + … + res[tok] = s.
return res[v] = (h[v] <=
d[v]) ? 1 : s;
}
Основная
часть программы. Читаем входные данные. Строим граф.
scanf("%d", &n);
g.resize(n + 1);
for (i = 0; i < n - 1; i++)
{
scanf("%d %d", &a, &b);
g[a].push_back(b);
g[b].push_back(a);
}
Инициализируем
массивы.
d.resize(n + 1);
h.resize(n + 1);
res.resize(n + 1);
Запускаем
поиски в глубину. Первый поиск для каждой вершины v вычисляет значения d[v]
и h[v].
dfs(1);
dfs2(1);
Выводим
ответ – наименьшее количество
друзей, которое требуется для поимки бабочки.
printf("%lld\n", res[1]);